# Full text of "MICRO SPITBOL"

## See other formats

Computer Science Department TECHNICAL REPORT MICRO SPITBOL Robert B. K. Dewar Martin Charles Golumbic Clinton F. Goss October I979 Report No. Oil K) NEW YORK UNIVERSITY Department of Computer Science Courant Institute of Mathematical Sciences 251 MERCER STREET, NEW YORK, N.Y. 10012 MICRO SPITBOL By Robert B. K. Dewar Martin Charles Golumbic Clinton F. Goss October I979 Report No. Oil This material is based upon work supported in part by the National Science Foundation under Grant No. MCS78-O382O. Any opinions, findings, and conclusions or recommondations expressed in this publication are those of the authors and do not necessarily reflect the views of the National Science Foundation. Abstract A compact version of MACRO SPITBOL, a compiler/ interpreter for a variant of SNOBOLU, has been developed for use on microcomputer systems. The techniques for producing an implementation are largely automatic in order to preserve the integrity and portability of the SPITBOL system. These techniques are discussed along with a description of an initial implementation on a 65K byte minicomputer. An interesting theoretical problem which arises when using procedures which compact the interpretive object code is also analyzed. Keywords: SNOBOLii, Compiler, Interpretive code, Microprocessors, Portability, Weighted Interval Graph MACRO SPITBOL (1"! is a compiler/ interpreter for a variant of SNOBOLU (3), SPITBOL (k) , which has been implemented on a variety of large computers. MICRO SPITBOL is an adaptation of the system for use on micro and minicomputers which compiles a language identical to MACRO SPITBOL with the exclusion of real arithmetic. The goal was to preserve the structure and machine independence of the system while allowing for the added constraints imposed by small computers, particularly the severe limitations on memory and address size. We also intended that the process for implementing MICRO SPITBOL on a minicomputer be largely automated. In this way we preserve the integrity of the well-tested MACRO SPITBOL source code while allowing for easy updating to new versions. These goals were attained by encoding the MACRO SPITBOL source code, written in the MINIMAL assembly language (5), into a compact microcomputer assembly language, MICRAL. In a MACRO SPITBOL implementation the MINIMAL source code is translated into the target machine's assembly language and directly executed; The target MICRO SPITBOL machine emulates a standard virtual microcomputer (MICRAC) which executes MICRAL code. This interpretive approach preserves the portability of MINIMAL programs while dealing with the problems and constraints imposed on MICRO SPITBOL. MICRO SPITBOL is implemented on the Incoterm SPD 20/U0 (6), a 65K byte minicomputer, and versions are in preparation for microcomputers based on the IMS 808O and M68OO processors. Th Incoterm implementation has been exercised with an extensive test package and appears very sound. It provides about 2/5 of memory for the user heap in which UOO to 500 SPITBOL statements may be compiled. The current version executes an average of 20 SPITBOL statements per second; This is l/lUO the execution speed of the CDC 6600 version. MICRAL - Micro Computer Assembly Language MICRAL (2) is an encoding of MINIMAL suitable for direct translation to an interpretive form to run on a mini or microcomputer system with a I6 bit addressing structure and 8 bit bytes. The layout of a MICRAL program and the environment in which it runs are similar to that of a MINIMAL program. However, MICRAL source code is largely non-symbolic; Most of the work in converting MICRAL to its interpretive form involves address resolution, a feature available on even the most primative assemblers. Unlike MINIMAL, MICRAL assumes no minimum hardware configuration since its machine code is interpretive. In fact, the object code for a given MICRAL program does not vary among machines with the exception of absolute addresses. Thus the sophistication of the target machine's instruction set determines only the speed at which the MICRAL object code is interpreted and not the size of the code, as in MINIMAL. The general format of MICRAL source code is typical of many assembly languages. The opcode is one of 80 mnemonic instructions which is translated into a single byte (x'OO' to x'UF'). The operand field is a (possibly empty) series of items separated by commas. Each item is one of the following: 1) A two or four digit hexidecimal number which is assembled into one or two object bytes j 2) A five character label appearing in the MICRAL program or a system subroutine. This is eventually translated into the two byte absolute address of the label; 3) A five character label preceded by a '+' or '-'. This form of an address reference is used to generate a special single byte address which will be discussed later. To represent MINIMAL operands in MICRAL, the byte following the opcode is used to specify the format of the first two operands. This byte, the operand header byte, contains information about the first operand in its four low order bits and information about the second operand in its four high order bits. In frequent cases (references to the contents of the six virtual registers) , the MINIMAL operand is completely specified in the header byte. For example, the MINIMAL instruction < MOV WA,-(XS) > is encoded in MICRAL as < MOV 90 > since x'O' is the four bit code for the contents of the WA register and x'9' indicates the contents of the word indexed by (XS) with a pre-decrement on XS. If additional fields are required to fully specify a MINIMAL operand, they directly follow the operand header byte. The fields for the first two operands may be followed by a field for the possible third operand. For example, the MINIMAL < BEQ WA,=X'00FF' , LABEL > would be encoded as < BEQ BO, OOFF, LABEL > since x'B' indicates a literal value for the second MINIMAL operand. In accordance with the space efficient philosophy of MICRAL there are several modifications we apply to the language as we have described it. First we restrict all literal values and offsets to be in the range to x'7FFF' . This allows literals in the range to x'7F' to be expressed as a single byte whose value is x'80'+literal. In a similar style, we convert local memory references to a single byte by requiring that all labels in the MICRAL program and system routines take on a value less than x'8000'. We express a jump address, ADR, which is in the range (L - x'l+O') to (L + x'3F') (where L is the current location) as a single byte containing (L + x'CO' - ADR). These short branch instructions are recognized during the translation from MINIMAL to MICRAL and are indicated by substituting '-LABEL' or '+LABEL' for 'LABEL' whenever LABEL is in range. The final and most space efficient optimization employed is the use of macros. MICRAL macros utilize the I76 unused opcodes x'50' to x'FF' for representing sequences of bytes in the MICRAL object code. These sequences of bytes may be a single MICRAL instruction, part of an instruction, or several instructions. Note that macros never include bytes corresponding to the one byte offset form of jump addresses, so the question of where to count the offset from does not arise. Also, a macro opcode may never be substituted for a sequence of bytes which have an embedded label in the source code. This eliminates jumping into the 'middle' of a macro. Also, it is not possible to embed a macro in another macro, thus eliminating the necessity for environment stacking when interpreting the macros. Macros may be interpreted by the MICRAC emulator in one of two ways. A table of the MICRAL bytes corresponding to each macro may be referenced when a macro is encountered. The emulator interprets the bytes obtained from the macro table as if they had appeared in the MICRAL program. The number of bytes for each macro is also maintained within the macro table and, when the macro bytes are exausted, interpretation returns to the main byte string. Alternately, some or all of the macros may be directly hand encoded into the target machine language. This latter approach requires more space, but increases execution speed. The PD/FMS Implementation The Incoterm SPD 20/i+0 is a byte oriented single address minicomputer with indexing and multi-level indirect addressing. It supports up to 65K bytes of magnetic core memory with a cycle time of 1.6 microseconds. MICRO SPITBOL is implemented under the Program Development/File Management System (PD/FMS) (7) which provides for task control and device handling via a package of relocatable routines. Minimum hardware for running MICRO SPITBOL consists of the central processor with 65K bytes of memory, a CRT/keyboard unit, and a 10 megabyte cartridge disk drive. Additional supported hardware includes 7 CRT/keyboard units, a printer, and 3 cartridge disk drives. The details of the PD/EMS implementation were as follows: The MACRO SPITBOL source code, written in MINIMAL, was translated to MICRAL source code by MICTRAN, a program coded in SPITBOL. It is a variation of a SPITBOL translator used for generating native assembly code from MINIMAL. It recognizes the short form of literals and branch instructions as described earlier. The program was run on a CDC 6600 and processed the 10,000 MINIMAL instructions in 20 cpu seconds. Figure 1 is an example of the code produced by MICTRAN. The MICRAL source code along with the error text file were then exported to the Incoterm system where the remainder of the implementation was done. The next stage was to determine the sequences of macros to employ in translating the MICRAL source code to SPD assembly code (8). We first examined the problem theoretically to determine whether there is an algorithm for giving optimal or near optimal results. The problem is interesting since, although the computation may be performed in polyiiomial time, the complexity of the optimal algorithm is a polynomial whose degree depends on the number of macros chosen: finding the u macros which minimize the length of t\ bytes of object code is OCC'H't) /(d-2).') where -t is the maximum length of a macro. Another approach which produces near optimal results and does allow embedding of macros requires 0(i:)(T)+-^'£logpT]) ) time. The analysis of this problem is presented in the appendix. In practice, this theoretical complexity is troublesome since version 3.3B of MICRO SPITBOL requires 23,110 bytes of MICRAL object code before macro substitution. Also, implementation of the algorithms analyzed in the appendix is difficult due to the numerous constraints on the allowable macros. Since macros may not contain short branches or embedded labels, choosing macros must be done from the source code and not the resulting byte string. Also, since additional short branches become available as macros are introduced, the computation of the length of the object code after a macro substitution is dependent on many factors. Due to the desire for a speedy implementation, it was decided to restrict macros to a single instruction or part of an instruction and no use of hand encodings or short branches was made. The MICRAL source code was sorted lexicographically with the opcode field as the first key and the operand field as the second key. The sorted list was then scanned by hand to count the number of each operational MICRAL instruction or part instruction. The number of bytes saved by converting each sequence to a macro was then computed for each such instruction and multiplied by the number of occurrences. The I76 byte sequences which produced the highest savings were chosen as macros. The MICRAL source code and the chosen macros were then processed by MICASM, which translates MICRAL to SPD assembly source code (see Figures 2 and 3). This program is coded in SPD assembly language and processes 65 lines per second. The resulting assembly language file was then assembled into a relocatable module. The size of that module with macro substitutions is 17,920 bytes, an improvement of 5,190 bytes over the corresponding module without macro substitutions. 7 To interpret the MICRAL object code, another module was included in the absolute assembly. This module, known as the MICRAC emulator, consists of 3,020 lines of code and takes 2,230 bytes of memory. Since its size is small compared to the MICRAL object code, the emulator is one area of the system in which speed considerations took priority over space. Finally, a set of modules consisting of PD/FMS routines for task control, timer control, and screen, disk, and printer handling were included in the absolute assembly. These routines are accessed by SPITBOL through a set of system routines which are called directly by the MICRAL code. The system routines were coded in SPD assembly language and are part of the mainline MICRO SPITBOL file (the absolute assembly). In addition to the system routines, this file contains the macro sequences and allocates space for the relocatable modules and the SPITBOL heap. It is 51^0 lines of code and occupies the full 65K bytes, 28k bytes of which are the user heap. The PD/FMS implementation has been exercised on a variety of test programs and appears very stable. Performance evaluation was done with a package of 2k programs which have an average length of 70 statements. The test set was run under version 3.3B of MACRO SPITBOL on the CDC 66OO for comparison. MICRO SPITBOL compiled at an average rate of I.3 statements per second and executed at 19.7 statements per second. The corresponding values for MACRO SPITBOL were I86.9 statements per second for compilation and 2,829 statements per second for execution. Conclusion The implementation of MICRO SPITBOL was broken down into two major stages. First, the design and implementation of programs for converting from MINIMAL to the interpretive MICRAL code, choosing appropriate macros, and converting from MICRAL to assembly language, required about three man-months work. The second stage entailed work specific to the PD/FMS implementation. This included coding the MICRAC emulator and system routines in SPD assembly language which, for the PD/FMS implementation, took about 1 man-month work. For subsequent implementations it is only this latter stage which is needed since the MICRAL object code and macros are fixed for a given version of MICRO SPITBOL and only minor changes in MICASM are necessary to accomodate various native assembly language formats. Also, since the process of translation for MICRAL is now automated, any program coded in MINIMAL may now be implemented by this scheme. The PD/FMS version currently allows lj-00 to 500 'typical' SPITBOL statements to be compiled. Again, since the MICRAL object code does not vary among implementations, this figure should remain fairly constant for microcomputers with 65K bytes of memory. The cost of the extra level of interpretation necessary to emulate the MICRAC machine is evident in the two order drop in execution speed from MACRO SPITBOL on the CDC 660O to the PD/FMS implementation. However, the Incoterm instruction set is rudimentary compared to other target microcomputers, so an improvement in execution speed may be expected on other processors. Extra speed may also be gained by utilizing some of the unused design features of MICRAL such as hand encodings for macros. Also, a better selection of 9 substitution macros will have a positive effect on both processing speed and space. Better macros may be selected by implementing one of the algorithms suggested in the appendix, with the possible addition of some efficient heuristics. Due to the decreasing cost of memory, the space constraints experienced in this implementation will probably disappear. Memory may become so inexpensive that a direct translation of the MINIMAL code to the target machine code would be preferable for small MINIMAL programs. However, for large MINIMAL programs, or on processors with a low level instruction set, the techniques used in the implementation of MICRO SPITBOL may be more suitable. Since these systems are typically single-user, the availability of very high level languages outweighs the loss of processing speed for many applications. 10 Appendix We now analyze the problem of finding a set of macro substitutions which minimizes the space required for the object code and macro table. We ignore the complications which arise when the short form of branches are used in the object code byte string since we have not implemented this aspect of MICRAL. Let B = <b]^,...,b^> be a sequence of bytes. The length of B is denoted |b| = ri. A subsequence of B, <b^,..,,b.>, is denoted B(i:j). A macro set is a set M = {m-|^, . . . ^m^) where each macro m^ is a sequence of bytes. The size of the macro table corresponding to M is given by ■0 Mm|| = I ItBil . i=l Since macros may not include a labelled byte other than the first byte, macros tend to be short compared to IbI. To aid in the analysis, we restrict the length of macros, Im. I < -t . A macro substitution is an operation on a byte sequence in which all occurrences of a given subsequence of bytes are replaced by a single byte. In case of overlapping occurrences of the subsequence, the leftmost occurrence is replaced. The byte sequence resulting from the substitution of all macros in a macro set, M, on a byte sequence, B, is denoted B(M) . The goal is to find, for a given byte sequence, B, a macro set, M, which minimizes the length function l(b,m) = |b(m)| + ||m|| 11 We shall analyze the worst case involved in a complete search strategy. For .1=1, the problem reduces to finding the best single macro for a byte sequence. Algorithm A performs this function using a table, FREQ, which maps subsequences of B onto a count of their occurrences in B. Algorithm A: 1) For k from 1 to ■t-'i-, perform steps 2 and 3- 2) For each subsequence of B, B(i:i+k.), increment FREQ(B( i : i+k) ) . 3) Set m(k) to a subsequence such that FREQ(m(k)) is maximal. Then set: L(B,{m(k)}) = |b| - (|m(k) !-l)*(FREQ(m(k))-l) + 1 h) The best macro is the m(i) which minimizes L(B,{m(k)}) in step 3, 5) Substitute the macro m(i) in B. Steps 2 and 3 are iterated over 0(-{,) times. Step 2 requires 0{t\) time to scan the subsequences and the map FREQ, if implemented as a balanced binary search tree, requires ©(loggT]) to maintain. Step 3 is linear if, during step 2, a pointer to the macro with the greatest FREQ is kept. Step h may also be done in this fashion in linear time. Performing step 5 may be done by a modification of the deterministic finite automaton pattern matching algorithm presented in Morris and Pratt (9) and expanded in Aho, Hopcroft, and Ullman (10) This algorithm requires 0(|b| + |m(i)|) = 0{T\+'t) time. Note that we perform step 5 by finding the leftmost occurrence of m(i), substitute for it, and continue to the right. Therefore, Algorithm A runs in OCi^+'tl-Ti'D-oggTi) time. For u > 1, one would expect that an iterative application of Algorithm A would be effective. However, an optimal choice for the first macro does not 12 necessarily lead to an optimal macro set. For example, if B=<j,a,b,c,d,e,f,m,r,h,a,b,c,d,e,g,k,c,d,e,f,n,s,h,a,b,c,p> a choice of m^ = <a,b,c,d,e> yields L(B,[m^}) = 25 which is optimal for io=l. However, any choice for ra will force L(B,(m^,m }) > 25. If ^-^ = <c,d,e,£> and m = <h,a,b,c>, then L(B,[m^}) = 26 and UB ,[m^,m^]) = 2U. Furthermore, our algorithm for pattern matching may not produce optimal results in cases where a macro overlaps itself. Substituting for the second occurrence in an overlapping pair may lead to a better choice for other macros. This forces the recognition of each occurence of a macro and treatment of overlapping occurences as separate cases. We now characterize the problem of finding an optimal macro set by a graph theoretic representation. A weighted graph G = (V,E,W) consists of a binary relation E over a finite set V of vertices, and an integer valued mapping W defined over V, G is an interval graph if its vertices can be put into 1-1 correspondence with a set of intervals on a line so that two vertices are adjacent if and only if their corresponding intervals intersect. If B is a sequence of bytes, G(B), the weighted interval graph corresponding to B, is defined as follows: Each vertex in V represents a substring of B which may be used as a macro j Vertices v. and v. are connected by an edge in E iff the occurrences of the substrings represented by V. and v. overlap in B. If V is a vertex representing an occurrence of the substring m, then W(v) = !m| - 1 . If S is a subset of vertices from V, the subgraph of G induced by S, denoted G , consists of all vertices of S together with all edges from E which connect those vertices. To construct G(B), the ©(rj-t) possible macros in B are scanned and one vertex is added to V for each. Whenever a vertex is added to V, edges are 13 added to E for each overlapping macro pair. Since adding edges takes O(-c^) time with efficient data structures for the graph, G(B) is constructed in OCri-t ) time. To find the macro set, M, which minimizes L(B,M), we apply the following algorithm: Algorithm B: 1) Calculate G(B). 2) Partition the vertices of G(B) such that each partition contains vertices which represent occurrences of identical substrings in B. 3) Let C be the set of all possible combinations of u partitions. For each set of combinations in C perform step h. k) Let S be the vertices in the D partitions. Let M be the macro set consisting of the u distinct byte sequences corresponding to the vertices of S. Occurrences of the macros in M are chosen in B such that no occurrences overlap. The problem of choosing the best set of occurrences is analogous to finding the maximum weighted independent set of vertices, I , in G . Then L(B,Mg) = |B| - I W(v) + I W(s) . vel seS 5) The macro set, M, which minimizes L(B,M) is then determined by choosing an M which minimizes L(B,M ) in step h. o o Gilmore and Hoffman (11) characterized interval graphs by showing them to be a subclass of chordal graphs. This class of graphs has the property that, for every simple cycle [v, ,v , ,,.,v ,v ] (n>3), there is an edge (v.,v.) in E such that v. and v. are in the cycle but the edge is not. 1 J 1 J ■' ^ 11; 2 Gavril (12) gives an 0(|v| ) algorithm for finding the maximum weighted independent set of a chordal graph. The algorithm is also presented in Golumbic(13) with suitable data structures. See also Booth and Leuker (lU). , 2 Thus, step 3 nisy be performed in 0((utv) ) time (note that the number of vertices in any induced subgraph is bounded by i:)ri). Step 3 must be performed at most (^ ; times. Hence, the worst case time complexity of algorithm B is o((Tl^^ + {^y^f (^3) , which is, in terms of the length of the input string, a polynomial whose degree depends on the constant u. In the example of this paper, r] is 23,000, u is 176, and a reasonable -t would be 20. With values in this range, the above complexity approximates and is bounded by o((^^)'^^ / (13-2):) . Since the time complexity of Algorithm B is high for this application, an effective algorithm for finding a near optimal solution is needed. One such heuristic approach would', be an iterative application of Algorithm A whose time complexity is 0(u(Ti+^^Log2Ti)) . Such an approach may potentially produce better results than Algorithm B since it allows the embedding of macros within other macros, a feature prohibited in Algorithm B. Although, one could theoretically include this embedding feature in a method similar to Algorithm B by using the weighted overlap graph model as described in Gavril (15) and Golumbic( I3) • 15 EXIXR EXIXR RTN MOV 9k MOV XR,-(XS) STACK RESULT EXITS EXITS RTH LCW 014 LCH XR LOAD CODE WORD MOV 37 MOV (XR),XL LOAD ENTRY ADR BRI 03 BRI XL EXECUTE NEXT CODE EXNAM EXNAF RTN MOV 93 MOV XL,-(XS) STACK NAh'E BASE MOV 90 MOV WA,-(XS) STACK NAME OFSET BRN EXITS BRN EXITS DO NEXT CODE WORD EXNUL EXNUL RTN MOV 9B, NULLS MOV =NULLS,-(XS) STACK NULL VALUE BRN EXITS BRN EXITS DO NEXT CODE WORD FXSID EXSID RTN MOV OA 25 MOV CURID,WA LOAD CURRENT ID BNE B0!7FFF,+EXSI1 BNE WA, =CFP$M, EXS I 1 JUMP NO OVFL ZER 00 ZER WA RESET FOR V/RAP EXSIl ICV 00 EXSIl ICV WA BUMP ID VALUE MOV AO 25 MOV WA^CURID STORE FOR NEXT MOV EO'82 MOV WAJDVAL(XR) STORE ID VALUE BRN ExixR BRN EXIXR EXIT WITH RESULT Figure 1. Example of MINIMAL code (right) translated to MICRAL (left) by MICTRAN. 16 EXIXR EQU $ EXIXR HEX 329U EXITS EQU $ EXITS HEX 2A0tt HEX 3237 HEX 0B03 EXNAM EQU $ EXNAM EXNUL EQU $ EXNUL EQU $ HEX 329U EQU $ HEX 2A0tt HEX 3237 HEX 0B03 EQU $ HEX 3293 HEX 3290 HEX 030C ADDR EXITS EQU $ HEX 329B ADDR NULLS HEX n30C ADDR EXITS EQU $ HEX 320A25 HEX 09B07FFF ADDR EXSIl HEX UUOO HEX ICOO HEX 32A025 HEX 32E082 HEX 03 ADDR EXIXR EXSID EQU $ EXSID EXSIl HEX ICOO EXSIl MOV 91+ STACK RESl'LT LCW Ok LOAD NEXT CODE WORD MOV 37 LOAD ENTRY ADDRESS BRI 03 EXECUTE NEXT CODE MOV 93 STACK NAME BASE MOV 90 STACK NAME OFSET BRN EXITS DO NEXT CODE WORD MOV 9B, NULLS STACK NULL VALUE BRN EXITS DO NEXT CODE WORD MOV 0A,25 LOAD CURRENT ID BNE B0,7FFF ,+EXSIl ZER 00 RESET FOP WRAP ICV 00 BUMP ID VALUE MOV A0,25 STORE FOP NEXT T MOV EG, 82 STORE ID VALUE BRN EXIXR EXIT WITH RESULT ME Figure 2. Example of translation from MICRAL to SPD assembly code with no macro substitution. 17 EXIXR EQU $ EXIXR HEX 6A *** MOV 9k STACK RESULT EXITS EQU $ EXITS HEX 2A0I+ LCW OU LOAD NEXT CODE WORD HEX 89 *** MOV 37 LOAD ENTRY ADDRESS HEX 0B03 BRI 03 EXECUTE NEXT CODE EXNAM EQU $ EXNAM HEX 68 *** MOV 93 STACK NAME BASE HEX 60 *** MOV 90 STACK OFSET HEX El *** BRN EXITS DO NEXT CODE WORD EXNUL EQU $ EXNUL HEX 68 *** MOV 9B, NULLS STACK NULL VALUE ADDR NULLS HEX El *** BRN EXITS DO NEXT CODE WORD EXSID EQU $ EXSID HEX 9A *** MOV 0A,25 LOAD CURRENT ID HEX 25 HEX EC *** BNE BO, 7FFF^ +EXSI 1 HEX 7FFF ADDR EXSIl HEX ttUOO ZER 00 RESET FOR WRAP EXSIl HEX ICOO EXSIl I CV 00 BI'MP ID VALUE HEX 67 *** MOV A0,25 STORE FOP NEXT TIME HEX 25 HEX 5D *** MOV E0,82 STORE ID VALUE HEX EO *** BRN EXIXR EXIT WITH RESULT Figure 3. Example of translation from MICRAL to SPD assembly code with macro substitutions. <***> indicates the use of a macro. 18 Bibliography 1) Dewar, R.B.K. and McCann, A. P., 'MACRO SPITBOL - a SNOBOLU Compiler', Software - Practice and Experience, 7 (I977), pp. 95-113. 2) Dewar, R. B. K. and Goss, C. F. , MICRAL - Language Description and Documentation , available from the authors. 3) Priswold, R.E,, Poage, J.F. , and Polonsky, I. P., The SNOBOLli Programming Language , Second Edition, Prentice-Hall, Englewood Cliffs, N.J., 256 pp., 1971. h) Dewar, R.B.K. , 'SPITBOL Version 2,0', IIT Internal Report, 78 pp., I97I. 5) Dewar, R.B.K., McCann, A. P., 'MINIMAL - A Machine Independent Assembly Language', Computer Science Department Technical Report, Courant Institute of Mathematical Sciences, No. 012. 6) SPD 20/20 Multi - station Intellegent Terminal System - System Description , Incoterm Corp., Wellesley Hilla, Mass., 02181, MS-7I65.I, January, I976. 7) PD/FMS Programmers ' Reference Manual , Incoterm Corp., Wellesley Hills, Mass. , 02181, MS-7233.6. 8) Incoterm SPD Assembly Language , Incoterm Corp., Wellesley Hills, Mass., 02181, MS-7215.2. 9) Morris, J.H. and Pratt, V. R, , 'A linear pattern matching algorithm'. Tech. Report No. i+O, Computing Center, University of California, Berkley (I97O). 10) Aho, A. v., Hopcroft, J.E., and Ullman, J.D. , The Design and Analysis of Computer Algorithms . Addison -Wesley , I976. 11) Gilmore, P.C. and Hoffman, A.J., 'A characterization of comparability graphs and of interval graphs', Canadian Journal of Mathematics, 16 (196U), pp. 539-5it3. 19 12) Gavril, F. , 'Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph' SIAM Journal of Computing, 1 (I972), No. 2, pp. I8O-I87. 13) Golumbic, M.C. , Algorithmic Graph Theory and Perfect Graphs , Academic Press. New York, N.Y., I96O . Ill) Booth, K.S. and Leuker, G. S., 'Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms', J. Computer Sys. Sci. , 13(1976), 335-379. 15) Gavril, F. , 'Algorithms for a maximum clique and a minimum independent set of a circle graph', Networks, 3(1973), 261-273. This book may be kept FOURTEEN DAYS A fine will be charged for each day the book is kept overtime. 1 CAYLORD 142 NYU Comp.Sci.Dept . TR-011 Dewar MICRO SPITBOL. C.2 NYU " Com^pjSgj^Dept. Dewar C.2 AUTHOR MICRO SPITBOL. TITLE DATE DUE BORROWER'S NAME N.Y.U. Courant Institute of Mathematical Sciences 251 Mercer St. New York, N. Y. 10012